package com.clstu.stack;

import java.util.Scanner;

/**
 * 用链表实现栈结构,优点,
 */
public class LinkedListStackDemo {
    public static void main(String[] args) {
        //测试是否写对
        //创建栈
        LinkedListStack lss = new LinkedListStack(4);
        //用菜单
        String key = "";//接受游湖输入
        Scanner scanner = new Scanner(System.in);
        boolean loop = true;
        while (loop){
            System.out.println("\n======测试栈(链表版本)==========");
            System.out.println("  push: 入栈");
            System.out.println("  pop:  出栈");
            System.out.println("  look: 查看栈");
            System.out.println("  peek: 看栈顶");
            System.out.println("  exit: 退出程序");
            System.out.print("  请输入:");
            key = scanner.next();
            switch (key){
                case "push":
                    System.out.print("请输入要入栈的数:");
                    lss.push(new Node(scanner.nextInt()));
                    break;
                case "pop":
                    try {
                        System.out.println("出栈:"+lss.pop());
                    } catch (Exception e) {
                        e.printStackTrace();
                    }
                    break;
                case "look":
                    lss.look();
                    break;
                case "peek":
                    try {
                        System.out.println("栈顶:"+lss.peek());
                    } catch (Exception e) {
                        e.printStackTrace();
                    }
                    break;
                case "exit":
                    loop =false;
                    break;
            }
        }
        System.out.println("程序结束~~~");
    }
}

/**
 *  链表栈类
 */
class LinkedListStack{
    private int maxSize;//最大有效数据个数
    private int curSize;//当前有效数据个数
    private Node head = new Node(0);//链表,用来存放数据
    private Node top = null;//栈顶

    //构造器
    public LinkedListStack(int maxSize){
        this.maxSize = maxSize;
        curSize = 0;
    }

    //是否栈空;
    public boolean isEmpty(){
        return head.getNext() == null;
    }

    //是否栈满
    public boolean isFull(){
        return curSize == maxSize;
    }

    //入栈
    public void push(Node node){
        //先判断是否栈满
        if(isFull()){
            System.out.println("栈满,入栈失败");
            return;
        }
        //入栈,top永远指向链表的第一个元素
        node.setNext(top);
        top = node;
        //head.next也跟着指向第一个元素
        head.setNext(top);
        curSize++;
    }

    //出栈
    public int pop(){
        //先判断是否栈空
        if(isEmpty()){
            throw new RuntimeException("栈空,出栈失败");
        }
        //出栈,弹出链表的第一个数据
        Node val = top;
        //原先的top会因为没有变量再指向它而被垃圾回收机制回收
        top = top.getNext();
        head.setNext(top);
        curSize--;
        return val.getData();
    }

    //显示栈内所有的元素
    public void look(){
        //先判断是否栈空
        if(isEmpty()){
            System.out.println("栈空,没有数据");
            return;
        }
        //显示所有数据
        Node cur = head.getNext();
        int n = curSize;
        while (true){
            //如果到最后
            if(cur==null){
                return;
            }
            //显示数据
            System.out.println("Node"+(n--)+": "+cur.getData());
            //后移
            cur = cur.getNext();
        }
    }

    //编写方法查看栈顶,不出栈
    public int peek(){
        //先判断是否栈空
        if(isEmpty()){
            throw new RuntimeException("栈空,查看栈顶失败");
        }
        return top.getData();
    }
}

/**
 * Node节点类
 */
class Node{
    private int data;
    private Node next;//next

    //构造器
    public Node(int data){
        this.data = data;
    }

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }

}
